In questa sessione vi sarà presentata la formulazione di modelli di programmazione lineare attraverso un semplice problema di prodotto misto chiamatoLa miglior panetteria.
Lo scopo di questa sessione è introdurre i concetti base di:
Dovete identificare questi concetti nella formulazione di modelli di programmazione lineare.
Il primo passo nella formulazione di un modello è identificare e dare dei nomi alle variabili di decisione. Le variabili di decisione sono gli elementi del modello che il decision maker controlla e quei valori che determinano la soluzione del modello.
Il prossimo passo è l'identificazione della funzione obiettivo in termini di variabili di decisione. La funzione obiettivo si trova dove specificate lo scopo che state tentando di raggiungere. Lo scopo può sia essere la massimizzazione, sia la minimizzazione del valore della funzione obiettivo. A volte usiamo l'espressione "voler ottimizzare il modello". Questo significa che vogliamo trovare i valori delle variabili di decisione che esprimono sia il massimo, sia il minimo valore della funzione obiettivo. In molti casi, la funzione obiettivo ha un valore monetario, per esempio massimizzare il profitto o minimizzare il costo, sebbene non sia sempre così.
I vincoli sono le reali limitazioni nelle variabili di decisione. Un vincolo restringe o vincola I valori possibili che la variabile può assumere. Per capire come può essere un vincolo, prendiamo come esempio la limitazione delle risorse quali capienza della macchina e forza lavoro.
La miglior panetteria di pane è famosa per il suo pane. Ne produce di due tipi:"Sunshine", un pane bianco e "Moonlight", un grande pane scuro.
Il mercato per questo famoso pane è senza fine. Ogni pagnotta di Sunshine venduta porta un profitto di $0.05 e ogni pagnotta Moonlight porta un profitto di $0.08. Esiste un costo fisso di funzionamento della panetteria di $4000 al mese, a dispetto della quantità di pane prodotto.
La panetteria è divisa in due reparti: cottura e miscelazione, con capacità limitate in entrambi i reparti.
Nel reparto di cottura ci sono dieci grandi forni, ciascuno con una capacità di 140 infornate al giorno.C'è la possibilità di mettere dieci pagnotte di Sunshine in ognuna di queste infornate, o cinque delle più grandi Moonlight. Si può fare ogni combinazione dei due diversi tipi di pane nelle infornate. Basta tenere a mente che ogni pagnotta di Moonlight occupa due volte lo spazio di una di Sunshine.
Il reparto di miscelazione può miscelare fino a 8000 pagnotte di Sunshine al giorno e fino a 5000 pagnotte di Moonlight. Ci sono due separate miscelatrici automatiche così che non ci sia conflitto nella preparazione dei due tipi d' impasti.
Poichè il mercato per entrambi i due tipi di pane è illimitato, la direzione della BBB ha deciso di trovare la miscela migliore di prodotto. La questione è quante pagnotte di ogni tipo di pane dovrebbero essere cotte al giorno al fine di produrre il profitto più alto, tenendo conto delle limitazioni fisiche del forno.
Ora vi mostriamo come identificare le variabili di decisione, la funzione obiettivo e i vincoli per questo modello e poi introdurremo la formulazione in MPL.
Per la nostra panetteria, le variabili di decisione corrispondono al numero di pagnotte di ogni tipo di pane prodotto al giorno. Per fare una formulazione più semplice da leggere, è buona idea assegnare nomi alle variabili di decisione, che ci permettono d'identificare cosa rappresentano realmente. Usare due variabili di decisione, chiamate Sun e Moon, e ammetere che abbiano i seguenti significati:
Sun = Numero delle pagnotte di Sunshine prodotte al giorno
Moon = Numero di pagnotte di Moonlight prodotte al giorno
Ora si vuole determinare i valori per queste due variabili di decisione così da massimizzare il profitto della panetteria.
Nel nostro esempio, lo scopo è massimizzare il profitto giornaliero. Ricaviamo un profitto di $0.05 per ogni pagnotta di Sunshine, dunque la produzione giornaliera di Sunshine renderà $0.05 moltiplicati per il valore della variabile di Sun per profitto.
Per la produzione di Moonlight, la resa corrispondente è $0.08 moltiplicata per il valore della variabile di Moon. Chiamiamo i valori $0.05 e $0.08 i coefficienti per le corrispondenti variabili di decisione nella funzione obiettivo. Per avere il contributo totale per il profitto giornaliero, aggiungiamo i contributi dai due tipi di pane, Da questo, sottraiamo il costo fisso di $4000 diviso per 30 giorni in un mese, per ottenere il profitto netto al giorno. Questo conduce alla seguente quantità che vogliamo massimizzare:
Profitto = 0.05 Sun + 0.08 Moon - 4000/30
Abbiamo ora definito la funzione obiettivo per questo particolare problema. Il solver usa la funzione obiettivo come un criterio che determini quale sia la soluzione ottimale.
Il primo vincolo nel reparto di cottura è complicato dato che non c'è interazione tra i tipi di pane. Cè la possibilità di cuocere sia dieci Sunshine sia cinque Moonlight in ogni infornata. Esiste, inoltre, la possibilità, di usare ogni combinazione dei due.L'espressione 1/10 Sun + 1/5 Moon ci fornisce il totale utilizzo delle infornate.Se si misura la capacità di ogni forno come numero d'infornate che si possono fare al giorno (10 x 140), si può esprimere il vincolo come:
1/10 Sun + 1/5 Moon <= 10 x 140
Esprimiamo i vincoli che vengono dati dal reparto di miscela così:
Sun <= 8000
Moon <= 5000
Abbiamo ora definito la funzione obiettivo e tutti i vincoli ; questa è la formulazione di un problema di programmazione lineare come mostrato di seguito:
Max
Profit = 0.05 Sun + 0.08 Moon - 4000/30
Subject to
1/10 Sun + 1/5 Moon <= 10 x 140
Sun <= 8000
Moon <= 5000
Una volta che avete la vostra formulazione, la maggior parte del lavoro è fatta. Come potete notare MPL accetta il suo input in una forma simile a quella appena scritta.
Avviare l'applicazione MPL.
Scegliere New (Nuovo) dal menu File (Archivio) per creare un nuovo file di modello vuoto.
Scegliere Save As (Salva come) dal menu File (Archivio) e salvare il file come Bakery2.mpl.
Siete, ora, pronti per tradurre il modello in linguaggio MPL. L'editor del modello in MPL è un editor standard di testo che vi permette di tradurre il modello e realizzare diverse operazioni di editing nel testo del modello. Introdurre le seguente formulazione del modello, nel suo editor:
TITLE BetterBreadBakery;
MAX
Profit = 0.05 Sun + 0.08 Moon - 4000/30;
SUBJECT TO
1/10 Sun + 1/5 Moon <= 10 * 140;
Sun <= 8000;
Moon <= 5000;
END
Si noti che esiste una piccola differenza tra la formulazione nel passo precedente e nel file mostrato qui. C'è un punto e virgola ';' dopo la funzione obiettivo e dopo ogni vincolo. Questo permette ad MPL di separare i vincoli.
L'indentazione usata tra le entrate e le linee in MPL non è rigida. Si raccomanda, quando s'introduce un modello, di usare spazi e extra linee per far sì che la formulazione del modello sia più semplice da leggere e da comprendere. MPL riguarda solo il testo reale nel file del modello.
Quando si è terminata l'introduzione del modello, scegliere Save (Salvare) dal menu File (Archivio) per salvarlo.
Dopo aver introdotto la formulazione nell'editor del modello, potete controllare gli eventuali errori presenti nella sintassi. Se MPL dovesse trovare un errore nella formulazione lo riporterà nella finestra Error Message (Messaggio d'Errore) mostrando la linea errata nel modello, insieme ad una breve spiegazione del problema. Il cursore è automaticamente posizionato sull'errore nel file del modello, con la parola sbagliata sottolineata.
Ora, per controllare la sintassi, scegliere Check Syntax (Controllo Sintassi) dal menu Run (Eseguire). Se non si trova alcun errore, MPL fornirà un messaggio che dichiari che la sintassi del modello è corretta. Se, invece, viene trovato un errore all'interno del modello, MPL mostrerà una finestra con un Messaggio d'Errore (Error Message).
Se non trovate alcun errore nella vostra formulazione (congratulazioni!) potreste comunque vedere come funziona un messaggio d'errore. Vi introdurremo un errore nel modello; si noti come i messaggi d'errore di MPL possono aiutarvi a correggerlo.
Nell'editor del modello eliminare il punto e virgola alla fine del primo vincolo come segue:
SUBJECT TO
1/10 Sun + 1/5 Moon <= 10 * 140 ! note the missing semicolon
Sun <= 8000;
Moon <= 5000;
Scegliere Check Syntax (Controllo delle Sintassi) dal menu Run (Eseguire). MPL passerà in rassegna tutto il modello e troverà il punto e virgola mancante quando starà analizzando il secondo vincolo, mostrando il seguente messaggio d'errore:
Finestra con Messaggio d' Errore
La ragione per cui MPL non ha notato il punto e virgola mancante finchè non ha raggiunto il secondo vincolo, è perchè pensa che 10*140 sia un coefficiente per la variabile Sun nella linea sottostante.
Quando si preme il tasto OK si ritorna all'editor del modello. Il cursore verrà automaticamente posizionato nel punto in cui MPL ha trovato l'errore che, nel nostro caso, si trova al `<=' nel secondo vincolo.
Ora potete introdurre nuovamente il punto e virgola per il primo vincolo e se controllate la sintassi un'altra volta, MPL segnalerà che la sintassi è corretta.
Nel prossimo passo si dovrà trovare la soluzione al modello 'Bakery2.mpl'. La risoluzione del modello implica diverse mansioni per MPL, tra cui il controllo della sintassi,analisi del modello nella memoria, trasferire il modello al solver, trovare la soluzione al modello e poi recuperare la soluzione dal solver e creare il file di soluzione. Tutte queste mansioni sono fatte dall'utente quando sceglie il comando di risoluzione dal menu. Per trovare la soluzione al modello seguire questi passi:
Scegliere Solve CPLEX dal mene Run o premere il tasto Run Solve sulla Toolbar.
Mentre risolverete il modello, apparirà la Status Window (Finestra di Stato); questa vi fornirà le informazioni circa il progresso della soluzione.
Nel prossimo passo si dovrà trovare la soluzione al modello 'Bakery2.mpl'. La risoluzione del modello implica diverse mansioni per MPL, tra cui il controllo della sintassi,analisi del modello nella memoria, trasferire il modello al solver, trovare la soluzione al modello e poi recuperare la soluzione dal solver e creare il file di soluzione. Tutte queste mansioni sono fatte dall'utente quando sceglie il comando di risoluzione dal menu. Per trovare la soluzione al modello seguire questi passi:
Scegliere Solve CPLEX dal mene Run o premere il tasto Run Solve sulla Toolbar.
Mentre risolverete il modello, apparirà la Status Window (Finestra di Stato); questa vi fornirà le informazioni circa il progresso della soluzione.
La Finestra Stato per il modello Bakery2
Se tutto procede bene MPL visualizzerà il messaggio "Optimal Solution Found" (Trovata Soluzione Ottimale). Se c'è una finestra con un messaggio d'errore di sintassi, si controlli, per favore, la formulazione che avete introdotto precedentemente con il modello descritto in questa sessione.
Dopo aver risolto il modello, MPL, automaticamente, crea un file standard di soluzione, contenente diversi elementi della soluzione del modello. Questo include, tra le altre cose, il valore ottimale della funzione obiettivo, l'attività e i costi ridotti per le variabili, i prezzi di scarto e d'ombra per i vincoli. Questo file di soluzione viene creato con lo stesso nome del file di modello ma con l'aggiunta di '.sol'. Nel nostro caso il file di soluzione si chiamerà 'Bakery2.sol'.
Dopo aver risolto il modello, potete visualizzare il file di soluzione in una finestra di visione premendo il tasto View sul fondo della Status Window (Finestra di Stato). Questo visualizzerà la finestra di visione mostrata qui sotto.
Finestra di visione con il file di soluzione Bakery2.sol
La Finestra di Visione immagazzina il file di soluzione nella memoria, permettendovi di scorrere le soluzioni usando la scroll bars. Una completa lista del file di soluzione è mostrata qui di seguito:
MPL Modeling System - Copyright (c) 1988-1999, Maximal Software, Inc.
--------------------------------------------------------------------------------
MODEL STATISTICS
Problem name: BetterBreadBakery
Filename: Bakery2.mpl
Date: April 2, 1998
Time: 17:29
Parsing time: 0.04 sec
Solver: CPLEX
Objective value: 506.666666667
Iterations: 3
Solution time: 0.14 sec
Constraints: 3
Variables: 2
Nonzeros: 4
Density: 67 %
SOLUTION RESULT
Optimal solution found
MAX Profit = 506.6667
DECISION VARAIBLES
PLAIN VARIABLES
Variable Name Activity Reduced Cost
------------------------------------------------------
Sun 8000.0000 0.0000
Moon 3000.0000 0.0000
------------------------------------------------------
CONSTRAINTS
PLAIN CONSTRAINTS
Constraint Name Slack Shadow Price
------------------------------------------------------
c1 0.0000 -0.4000
c2 0.0000 -0.0100
c3 2000.0000 0.0000
------------------------------------------------------
END
La prima parte del file di soluzione contiene diverse statistiche per il modello, come nome del file, data e tempo in cui il modello è stato risolto, quale solver è stato usato, il valore della funzione obiettivo e la grandezza del modello.
La prossima parte del file di soluzione contiene i risultati della soluzione. Qui potete vedere se la soluzione che è stata trovata era ottimale, illimitata o impossibile. Vi viene, inoltre, mostrato il nome e il valore ottimale della funzione obiettivo. Nel nostro caso, Il profitto per la panetteria corrisponde a $506 al giorno.
Nella sezione che riguarda la VARIABILE DI DECISIONE trovate una lista di variabili nel modello, Sun e Moon. Noterete che per il tipo di pane Sun la soluzione vi consiglia di produrre 8000 pagnotte al giorno, che è la stessa quantità della capacità del reparto di miscelatura per lo stesso tipo di pane. Per quanto riguarda il tipo di pane Moon, la soluzione vi consiglia di produrre 3000 pagnotte al giorno, che è meno della capacità massima di 5000 pagnotte Moon al giorno per il reparto di miscelatura.
Nella sezione riguardante i VINCOLI, il file di soluzione elenca tutti i vincoli per il modello. Nel nostro modello, avevamo tre vincoli, uno per i forni nel reparto di cottura, e due vincoli nel reparto di miscelatura per ogni tipo di pane. Dato che lo scarto per il primo vincolo è zero, i forni nel reparto di cottura lavorano a pieno ritmo. Nella stessa maniera, le macchine per la miscela per il pane Sunshine lavorano a pieno ritmo, ma la macchina per la miscela di pane Moonlight ha uno scarto di 2000.
Dunque, dato che i forni nel reparto della panetteria vengono divisi tra due tipi di pane, il solver ha scelto di produrre quanto più pane di tipo Sunshine sia possibile, poi utilizzare il resto della capacità, per produrre il pane di tipo Moonlight.